package com.cat.binaryTree;

import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/merge-k-sorted-lists/
 * @create 2025/9/28 16:43
 * @since JDK17
 */

public class Solution77 {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        ListNode dummy = new ListNode(-1), p = dummy;
        for (var node : lists) {
            if (node != null) {
                heap.add(node);
            }
        }
        while (!heap.isEmpty()) {
            var q = heap.poll();
            p = p.next = q;
            if (q.next != null) {
                heap.add(q.next);
            }
        }

        return dummy.next;
    }
}
